package a07_二叉树;

/**
 * <p>
 * a08_完全二叉树节点的数量
 * 完全二叉树的定义：
 * 除了底层节点，上面的节点都是满的
 * 底层节点从左到右是连续的
 * 解法：
 * 满二叉树的节点数量：2的深度次方-1（n代表深度）
 * 到一定深度后，左节点和右节点一定为满二叉树
 * 那怎么判断是满二叉树：左边一直遍历和右边一直遍历的层数是一样的
 * 如果不是满二叉树继续往下遍历
 * </p>
 *
 * @author flyduck
 * @since 2024-08-29
 */
public class a11_完全二叉树节点的数量复习1 {

    public static void main(String[] args) {

        System.out.println((2 << 1) - 1);

        TreeNode root = new TreeNode(1,new TreeNode(2, new TreeNode(4,new TreeNode(8), new TreeNode(9)), new TreeNode(5,new TreeNode(10), new TreeNode(11))),new TreeNode(3, new TreeNode(6,new TreeNode(12), new TreeNode(13)), new TreeNode(7,new TreeNode(14), new TreeNode(15))));
//        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), null));
        System.out.println(countNodes(root));
    }



    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //增加终止条件，如果是完全二叉树，就需要直接返回了，不继续便利了
        int leftHeight = 0;
        TreeNode leftNode = root;
        while (leftNode != null){
            leftNode = leftNode.left;
            leftHeight++;
        }
        int rightHeight = 0;
        TreeNode rightNode = root;
        while (rightNode != null){
            rightNode = rightNode.right;
            rightHeight++;
        }
        if(leftHeight == rightHeight){
            //2的层数 -1
            //00010
            return (2 << (leftHeight-1)) - 1;
        }else {
            int leftNums = countNodes(root.left);
            int rightNums = countNodes(root.right);
            return leftNums + rightNums + 1;
        }
    }

    public static int countNodesForNormal(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftNums = countNodesForNormal(root.left);
        int rightNums = countNodesForNormal(root.right);
        return leftNums + rightNums + 1;
    }


}
